import java.util.*;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 20404
 * Date: 2023-01-31
 * Time: 13:19
 */

class MyQueue1 {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue1() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    public void swap1() {
        int len = stack2.size();
        for (int i = 0; i < len; i++) {
            stack1.push(stack2.pop());
        }
    }
    public void swap2() {
        int len = stack1.size();
        for (int i = 0; i < len; i++) {
            stack2.push(stack1.pop());
        }
    }
    public void push(int x) {
        swap1();
        stack1.push(x);
    }

    public int pop() {
        if(empty()) {
            return -1;
        }else {
            swap2();
            return stack2.pop();
        }
    }

    public int peek() {
        if(empty()) {
            return -1;
        }else {
            swap2();
            return stack2.peek();
        }
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    Stack<Integer> tmpStack;
    int dataFrom;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
        tmpStack = new Stack<>();
    }

    public void push(int x) {
        if(stack1.isEmpty()) {
            stack2.push(x);
            dataFrom = 2;
        }else {
            stack1.push(x);
            dataFrom = 1;
        }
    }

    public int pop() {
        if(empty()) {
            return -1;
        }else if(dataFrom == 1) {
            int len = stack1.size();
            for (int i = 0; i < len - 1; i++) {
                tmpStack.push(stack1.pop());
            }
            for (int i = 0; i < len - 1; i++) {
                stack2.push(tmpStack.pop());
            }
            dataFrom = 2;
            return stack1.pop();
        }else {
            int len = stack2.size();
            for (int i = 0; i < len - 1; i++) {
                tmpStack.push(stack2.pop());
            }
            for (int i = 0; i < len - 1; i++) {
                stack1.push(tmpStack.pop());
            }
            dataFrom = 1;
            return stack2.pop();
        }
    }

    public int peek() {
        if(empty()) {
            return -1;
        }else if(dataFrom == 1) {
            int len = stack1.size();
            for (int i = 0; i < len - 1; i++) {
                tmpStack.push(stack1.pop());
            }
            dataFrom = 2;
            int ret = stack1.pop();
            stack2.push(ret);
            for (int i = 0; i < len - 1; i++) {
                stack2.push(tmpStack.pop());
            }
            return ret;
        }else {
            int len = stack2.size();
            for (int i = 0; i < len - 1; i++) {
                tmpStack.push(stack2.pop());
            }
            dataFrom = 1;
            int ret = stack2.pop();
            stack1.push(ret);
            for (int i = 0; i < len - 1; i++) {
                stack1.push(tmpStack.pop());
            }
            return ret;
        }
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}




class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;
    int dataFrom;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if(queue1.isEmpty()) {
            queue2.offer(x);
            dataFrom = 2;
        }else {
            queue1.offer(x);
            dataFrom = 1;
        }
    }

    public int pop() {
        if(empty()) {
            return -1;
        }else if(dataFrom == 1) {
            int len = queue1.size();
            for (int i = 0; i < len - 1; i++) {
                queue2.offer(queue1.poll());
            }
            dataFrom = 2;
            return queue1.poll();
        }else {
            int len = queue2.size();
            for (int i = 0; i < len - 1; i++) {
                queue1.offer(queue2.poll());
            }
            dataFrom = 1;
            return queue2.poll();
        }
    }

    public int top() {
        if(empty()) {
            return -1;
        }else if(dataFrom == 1) {
            int ret = pop();
            queue2.offer(ret);
            return ret;
        }else {
            int ret = pop();
            queue1.offer(ret);
            return ret;
        }
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}



class MyCircularQueue {

    private int[] arr;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.arr = new int[k + 1];
    }

    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }else {
            arr[rear] = value;
            rear = (rear + 1) % arr.length;
            return true;
        }
    }

    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }else {
            arr[front] = 0;
            front = (front + 1) % arr.length;
            return true;
        }
    }

    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return arr[front];
    }

    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        return arr[(arr.length + rear - 1) % arr.length];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % arr.length == front;
    }
}
public class Test {

    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        System.out.println(myQueue.peek());
        System.out.println(myQueue.pop());
    }

    public static void main2(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.top());
    }
    public static void main1(String[] args) {
        Deque<Integer> deque = new LinkedList<>(); //双端队列,栈
        List<Integer> list = new LinkedList<>(); //双向链表
        LinkedList<Integer> list1 = new LinkedList<>();//栈or双向链表or双端队列
        Queue<Integer> queue = new LinkedList<>();//单向队列
        List<Integer> list2 = new ArrayList<>(); //顺序表（向上转型）
        ArrayList<Integer> list3 = new ArrayList<>();//顺序表(功能更多)
        Deque<Integer> deque1 = new ArrayDeque<>();//(数组实现)双向队列or栈
        Stack<Integer> stack = new Stack<>();//顺序栈
        List<Integer> list4 = new Stack<>();//顺序栈(向上转型)
        Queue<Integer> queue1 = new ArrayDeque<>();//(数组实现)单向队列
        ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();//栈or双端队列or顺序表(一般不怎么这么用)
    }
}
